Дерево (Tree) — это нелинейная иерархическая структура данных, которая моделирует организационные структуры реального мира (например, файловую систему или родословную). В отличие от линейной упорядоченности списков, стеков и очередей, суть дерева заключается в егоиерархичности (Hierarchical)ирекурсивности (Recursive).
1. Анатомия структуры дерева
- узел (Node): базовая единица, содержащая ключ (Key) и полезную нагрузку.
- корневой узел (Root): единственный узел без входящих ребер, являющийся началом дерева.
- ребро (Edge): единственная траектория, соединяющая узлы, представляющая отношения «родитель — потомок».
- листовой узел (Leaf): конечный узел, не имеющий потомков, естественная граница завершения рекурсии.
2. Двойственное восприятие рекурсивного определения
Мы можем понимать дерево с двух точек зрения:
графический взгляд
Несвязный, связный граф, состоящий из узлов и рёбер, где каждый узел (кроме корня) имеет ровно одного родителя.
Несвязный, связный граф, состоящий из узлов и рёбер, где каждый узел (кроме корня) имеет ровно одного родителя.
рекурсивный взгляд
Дерево либо пусто, либо состоит из корневого узла и нуля или более поддеревьев (Subtree).
Дерево либо пусто, либо состоит из корневого узла и нуля или более поддеревьев (Subtree).
Пример дерева HTML DOM
В HTML
<html> является корнем,<body> и <head> являются братьями. Каждый тег и его вложенные элементы образуют поддерево. Такая структура позволяет перемещать весь элемент <ul> и все его <li> не нарушая внутреннюю иерархию.